搜索与图论2.1 | 您所在的位置:网站首页 › dijkstra求最短路 ii › 搜索与图论2.1 |
一、简述
本节主要介绍一下 \(Dijkstra\) 算法。该算法主要用于解决单源最短路问题,且该问题中的边权不为负数。 二、Dijkstra算法基本思想:我们假定有一张没有负权的图,该图如下
对于数据范围较小,且为稠密图的可以使用邻接矩阵进行图的存储,该算法朴素版的时间复杂度为 \(O(n^2)\)。而数据范围大,稀疏图使用邻接表存储,并使用小根堆进行优化,时间复杂度为 \(O(mlogn)\)。 模板题AcWing849.Dijkstra求最短路 I 题目描述给定一个 \(n\) 个点 \(m\) 条边的有向图,图中可能存在重边和自环,所有边权均为正值。 请你求出 \(1\) 号点到 \(n\) 号点的最短距离,如果无法从 \(1\) 号点走到 \(n\) 号点,则输出 \(−1\)。 输入格式第一行包含整数 \(n\) 和 \(m\)。 接下来 \(m\) 行每行包含三个整数 \(x,y,z\),表示存在一条从点 \(x\) 到点 \(y\) 的有向边,边长为 \(z\)。 输出格式输出一个整数,表示 \(1\) 号点到 \(n\) 号点的最短距离。 如果路径不存在,则输出 \(−1\)。 数据范围\(1≤n≤500,\) \(1≤m≤10^5,\) 图中涉及边长均不超过 \(10000\)。 输入样例 3 3 1 2 2 2 3 1 1 3 4 输出样例 3 C++代码 #include #include #include #include using namespace std; const int N = 510; int n, m; int g[N][N]; int dist[N]; bool st[N]; int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for(int i = 0; i < n; i ++) { int t = -1; for(int j = 1; j dist[j])) t = j; } for(int j = 1; j dist[ver] + w[i]) { dist[j] = dist[ver] + w[i]; heap.push({dist[j], j}); } } } if(dist[n] == 0x3f3f3f3f) return -1; else return dist[n]; } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while(m --) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, z); } int ans = dijkstra(); cout |
CopyRight 2018-2019 实验室设备网 版权所有 |